#pragma once
#include<iostream>
#include<vector>
#include<cassert>
using namespace std;

enum STATE
{
	EXIST,
	EMPTY,
	DELETE
};

template<class k,class v>
class Element
{
public:
	Element(const pair<k, v>& pr = pair<k,v>())
		:pa(pr)
		,sa(EMPTY)
	{}


	pair<k, v> pa;
	STATE sa;
};

template<class k>
class hashfunction
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};

template<>
class hashfunction<string>
{
public:
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};

template<class k,class v>
class _iterator
{
public:
	typedef _iterator<k, v> self;
	typedef _iterator<k, v> iterator;

	_iterator(vector<Element<k,v>>& mp)
	{
		_begin = start_begin = mp.begin();
		_end = mp.end();
		while (_begin != _end && _begin->sa != EXIST)
		{
			_begin++;
		}
	}	

	pair<k, v>& operator*()
	{
		return _begin->pa;
	}

	pair<k, v>* operator->()
	{
		return &_begin->pa;
	}

	self& operator++()
	{
		do
		{
			if (_begin == _end)
			{
				assert("Access out of bounds error");
				break;
			}
			_begin++;
			if (_begin == _end)
			{
				break;
			}
		}
		while (_begin->sa != EXIST);
		return *this;
	}

	self operator++(int)
	{
		self prev = *this;
		++(*this);
		return prev;
	}

	self& operator--()
	{
		do
		{
			if (_begin == start_begin)
			{
				assert("Access out of bounds error");
				break;
			}
			_begin--;
		}while (_begin->sa != EXIST);
		return *this;
	}

	self operator--(int)
	{
		self prev = *this;
		--(*this);
		return prev;
	}

	bool operator==(const iterator& it)
	{
		return this->_begin == it._begin;
	}

	bool operator!=(const iterator& it)
	{
		return !((*this) == it);
	}

	typename vector<Element<k, v>>::iterator _begin;
	typename vector<Element<k, v>>::iterator _end;
	typename vector<Element<k, v>>::iterator start_begin;

};

template<class k,class v,class hashfun = hashfunction<k>>
class OAHash
{
public:
	typedef _iterator<k, v> iterator;

	OAHash()
		:_size(0)
	{
		maping.resize(5);
	}

	iterator begin()
	{
		return iterator(maping);
	}

	iterator end()
	{
		iterator it(maping);
		it._begin = it._end;
		return it;
	}


	bool insert(const pair<k, v>& value)
	{
		hashfun hf;

		if (_size * 10 / maping.size() > 7)
		{
			OAHash<k,v,hashfun> newhashtable;
			newhashtable.maping.resize(maping.size() * 2);
			for (int i = 0; i < maping.size(); i++)
			{
				if (maping[i].sa == EXIST)
				{
					newhashtable.insert(maping[i].pa);
				}
			}
			maping.swap(newhashtable.maping);
		}

		size_t pos = hf(value.first) % maping.size();
		while (pos < maping.size() && maping[pos].sa == EXIST)
		{
			pos++;
		}

		maping[pos] =Element<k,v>(value);
		maping[pos].sa = EXIST;
		_size++;

		return true;
	}

	iterator find(const k& key)
	{
		hashfun hf;
		size_t pos = hf(key) % maping.size();
		while (pos < maping.size() && (maping[pos].pa.first != key || maping[pos].sa != EXIST))
		{
			pos++;
		}
		iterator it(maping);
		it._begin += pos;
		return it;
	}

	bool erase(const k& key)
	{
		hashfun hf;
		size_t pos = hf(key) % maping.size();
		while (pos < maping.size() && (maping[pos].pa.first != key || maping[pos].sa != EXIST))
		{
			pos++;
		}
		if (pos < maping.size())
		{
			maping[pos].sa = DELETE;
			_size--;
			return true;
		}
		return false;
	}

private:
	vector<Element<k, v>> maping;
	size_t _size;
};

